package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

/**
 * @author By ZengPeng
 */
public class 力扣_235_二叉搜索树的最近公共祖先 {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.initRoot();
        TreeNode root_0 = new TreeNode(1);
        TreeNode root_l = new TreeNode(2);
        System.out.println(lowestCommonAncestor(treeNode,root_0,root_l));
    }

    /**
     * 题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
     示例 1:
     输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     输出: 6
     解释: 节点 2 和节点 8 的最近公共祖先是 6。
     *
     * 分析：二叉搜索树的特点，
     *      如果p、q的值都小于root，说明p q 肯定在root的左子树中；
     *      如果p q都大于root，说明肯定在root的右子树中，
     *      如果一个在左一个在右 则说明此时的root记为对应的最近公共祖先
     *      1.递归  ：
     *      终止条件   左右节点都有返回，或者单节点返回
     *      单步操作  将直接点发展下去找 。 找到了返回
     *      返回值 当前节点  || null
     *
     * 边界值注意：
     *      1.不要考虑等于  等于时直接就返回当前记得了 ，因为能到这里，宁一个记得必定在自己下面
     **/
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(p.val>root.val && q.val>root.val)
            return lowestCommonAncestor(root.right,p,q);
        if(p.val<root.val && q.val<root.val)
            return lowestCommonAncestor(root.left,p,q);
        return  root;
    }
}
